# 冒泡排序
# 时间复杂度O(n2)
# 空间复杂度O(1)
def bubble_sort(data):
    """
    1. 获取当前数据的长度：len(data)
    2. 排序的轮次 len(data)-1，每轮交换的次数 len(data)- 排序轮次 - 1
    3. 如果data[i] > data[i+1] 则交换
    :param data: 初始列表
    :return: 返回排序后的列表
    """
    # n = len(data)
    # for i in range(n):
    #     for j in range(n-i-1):
    #         if data[j] > data[j+1]:
    #             swap = data[j]
    #             data[j] = data[j+1]
    #             data[j+1] = swap
    # return data
    num = 0
    for i in range(len(data)-1):
        for j in range(len(data)-i-1):
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]
                num += 1
                print(data, num)
    return data


def test_bubble_sort():
    assert bubble_sort([1, 4, 3, 7, 5]) == [1, 3, 4, 5, 7]
    assert bubble_sort([9, 5, 8, 3, 1]) == [1, 3, 5, 8, 9]





